package name.huzhenbo.java.algorithm.tree;

/**
 * The rebalance function still has some problems!!!
 *
 */
class BalancedBinarySearchTree {
    private Node root;
    private Node lowestInbalanceNode;

    public void insert(int val) {
        Node node = new Node(val, null, null);
        if (root == null) {
            root = node;
        } else {
            _insert(root, node);
            reBalance();
        }
    }

    // Insert new node, adjust balance factor of the tree, and find out the lowest inbalance node.
    // This node is the parent of smallest inbalance sub tree.
    // Do rebalance to this sub tree, all the nodes above still have the same balance factor as before this new item inserted.
    private void _insert(Node currentNode, Node node) {
        currentNode.balanceFactor += currentNode.getVal() > node.val ? 1 : -1;
        // revert back the balance factor of inbalance node, since all the nodes above smallest inbalance sub tree will
        // have the same balance factor after rebalance as before this new item inserted.
        if (currentNode.inbalance()) lowestInbalanceNode = currentNode;
        if (currentNode.getVal() > node.val) {
            if (currentNode.getLeft() == null) {
                currentNode.setLeft(node);
            } else _insert(currentNode.getLeft(), node);
        } else if (currentNode.getVal() < node.val) {
            if (currentNode.getRight() == null) {
                currentNode.setRight(node);
            } else _insert(currentNode.getRight(), node);
        }
    }

    /**
     * Do the rebalance to the smallest inbalance sub tree.
     * And readjust the balance factor of some nodes in this sub tree.
     */
    private void reBalance() {
        if (lowestInbalanceNode != null) {
            if (lowestInbalanceNode.balanceFactor > 0) {
                if (lowestInbalanceNode.left.balanceFactor > 0) {
                    Node leftNode = lowestInbalanceNode.left;
                    moveUp(leftNode);
                    lowestInbalanceNode.setLeft(leftNode.right);
                    leftNode.setRight(lowestInbalanceNode);
                    lowestInbalanceNode.balanceFactor = 0;
                    leftNode.balanceFactor = 0;
                } else {
                    Node leftRightNode = lowestInbalanceNode.left.right;
                    moveUp(leftRightNode);
                    lowestInbalanceNode.left.setRight(leftRightNode.left);
                    leftRightNode.setLeft(lowestInbalanceNode.left);
                    lowestInbalanceNode.setLeft(leftRightNode.right);
                    leftRightNode.setRight(lowestInbalanceNode);
                    leftRightNode.right.balanceFactor = leftRightNode.balanceFactor == 1 ? -1 : 0;
                    leftRightNode.left.balanceFactor = leftRightNode.balanceFactor == -1 ? 1 : 0;
                    leftRightNode.balanceFactor = 0;

                }
            } else {
                if (lowestInbalanceNode.right.balanceFactor < 0) {
                    Node rightNode = lowestInbalanceNode.right;
                    moveUp(rightNode);
                    lowestInbalanceNode.setRight(rightNode.left);
                    rightNode.setLeft(lowestInbalanceNode);
                    lowestInbalanceNode.balanceFactor = 0;
                    rightNode.balanceFactor = 0;
                } else {
                    Node rightLeftNode = lowestInbalanceNode.right.left;
                    moveUp(rightLeftNode);
                    lowestInbalanceNode.right.setLeft(rightLeftNode.right);
                    rightLeftNode.setRight(lowestInbalanceNode.left);
                    lowestInbalanceNode.setRight(rightLeftNode.left);
                    rightLeftNode.setLeft(lowestInbalanceNode);
                    rightLeftNode.right.balanceFactor = rightLeftNode.balanceFactor == 1 ? -1 : 0;
                    rightLeftNode.left.balanceFactor = rightLeftNode.balanceFactor == -1 ? 1 : 0;
                    rightLeftNode.balanceFactor = 0;
                }


            }
            lowestInbalanceNode = null;
        }
    }

    private void moveUp(Node rightNode) {
        if (lowestInbalanceNode == root) {
            root = rightNode;
            root.parent = null;
        } else {
            if (lowestInbalanceNode.parent.left == lowestInbalanceNode)
                lowestInbalanceNode.parent.setLeft(rightNode);
            else
                lowestInbalanceNode.parent.setRight(rightNode);
        }
    }

    public void traverse() {
        _traverse(root);
    }

    private void _traverse(Node node) {
        if (node == null) {
            return;
        }
        _traverse(node.getLeft());
        System.out.println(node.getVal());
        _traverse(node.getRight());
    }

    private class Node {
        private int val;
        private Node left;
        private Node right;
        private int balanceFactor;
        private Node parent;

        public Node(int val, Node left, Node right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }

        public int getVal() {
            return val;
        }

        public Node getLeft() {
            return left;
        }

        public void setLeft(Node left) {
            this.left = left;
            if(left != null) left.setParent(this);
        }

        public Node getRight() {
            return right;
        }

        public void setRight(Node right) {
            this.right = right;
            if(right != null) right.setParent(this);
        }

        public boolean inbalance() {
            if (Math.abs(balanceFactor) >= 2) {
                balanceFactor += (balanceFactor > 0 ? -1 : 1);
                return true;
            }
            return false;
        }

        public void setParent(Node parent) {
            this.parent = parent;
        }
    }
}
